This invention relates generally to cryptography and more particularly to a system and method for regenerating secret keys involved in Diffie-Hellman exchanges. Upon regeneration of secret keys, messages in secret communications are decrypted and observed.
Cryptography involves the encoding and decoding of messages, and has utility in the field of secure communications where issues of privacy and authentication of messages in public communications are important concerns. A privacy system prevents the extraction by unauthorized parties (xe2x80x9ceavesdroppersxe2x80x9d) of information from messages transmitted over a communication channel, thus assuring that only the intended recipient is able to read the message. An authentication system ensures detection of any modification of the message by unauthorized parties (xe2x80x9cintermeddlersxe2x80x9d), thus assuring the receiving party that the message is exactly what was sent by its sender. An authentication system also assures the recipient that the true sender actually sent the message. Depending upon safeguards, any communication channel may be threatened with eavesdropping or intermeddling, which thereby threatens the integrity of the messages or the identities of the transmitters.
FIG. 1 illustrates the flow of information in a conventional cryptographic communication. There are three parties: a transmitter 102, a receiver 104, and eavesdropper or intermeddlers 106. The transmitter 102 generates a message 108 to be communicated over a communication media 114 to the receiver 104. In order to prevent the eavesdropper or intermeddlers 106 from reading the messages, transmitter 102 encrypts the message 108 using an encryption key 110 producing encrypted message 112, which is sent to the receiver 104 over communications media 114. The legitimate receiver 104 must know how to decrypt the encrypted message 112 using decrypting key 116 to have access to the original message 108. The roles of transmitter 102 and receiver 104 are reversible, that is, a receiver 104 becomes a transmitter 102, which transmits encrypted messages 112 to the former transmitter 102, which in turn becomes receiver 104.
Encrypted messages in communication systems solve message security problems when message encryption techniques are properly used in the hands of legitimate personnel. However, in the hands of criminals or terrorists or other malicious parties, encrypted communications are an aid to illegal activities because the messages in the communications are secret to the public. The United States Government, motivated by a desire to prevent illegitimate activities, has required that it have access to encrypted communications so that it can observe the original, unencrypted messages 108. The government therefore has proposed various plans that require the parties involved in encrypted communications to hold in trust, or xe2x80x9cescrow,xe2x80x9d the encryption keys 110 used to encrypt messages 108 for some period of time. These encryption keys 110 must be readily surrendered to the government upon request. Having acquired the encryption keys 110, the government then has access to the original message 108 through decryption of the encrypted message 112 which are exchanged between suspect parties.
The requirement to hold encryption keys for a long period of time has great impact on embedded communications devices, especially network routers, as most routers do not have any hard disk or other memory devices to store encryption keys.
Additionally, it is desirable to implement a cryptographic scheme utilizing ephemeral keys which are derived from a Diffie-Hellman exchange, with one key per communication session. These ephemeral keys are then destroyed after each session. Federal law mandates access to keys for a period of up to seven years, requiring storage of hundreds of thousands of keys since hundreds of thousands of communication sessions may occur in a period of seven years with each session generating a unique key.
Moreover, it is desirable to embrace a standard where any key escrow scheme does not preclude interoperability with existing standards. For example, if one party implements a key escrow scheme and others do not implement that key escrow scheme, it is desirable that the party with the escrow scheme is not precluded from inter-operating with the others.
It is further desirable that a key escrow scheme can be seamlessly added to any standard-compliant key management protocol which utilizes a Diffie-Hellman exchange in order to additionally generate ephemeral secret keys such that the additional implementation which performs escrow remains fully standard-compliant. The escrow requirement thus raises the concern that the escrow of keys must be done securely, i.e., with full proof of security and authentication of a party that is depositing a key in escrow.
Attempts at escrowing ephemeral keys have been discussed by Silvio Micali, xe2x80x9cGuaranteed-Partial Key Escrow,xe2x80x9d MIT/LCS/TM-537, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass. (1995); and by Mihir Bellare and Shafi Goldwasser, xe2x80x9cVerifiable Partial Key Escrow,xe2x80x9d University of California, San Diego, CSE Department Technical Report. Both of these papers describe key escrow schemes that take advantage of a Diffie-Hellman exchange and allow for recovery of communications using a partially escrowed key. Each key used for bulk encryption by a router, for example, is partially escrowed. However, each of these schemes concerns only the partial escrow of a single ephemeral key, and does not deal with the problem of ephemeral session keys, where hundreds or thousands of keys are generated during a period of time of up to seven years.
A key escrow scheme applicable to network communications devices is discussed in xe2x80x9cEscrowed Encryption Standard (ESS),xe2x80x9d National Institute for Standards and Technology, Federal Information Processing Standards Publication (FIPS PUB) 185, 1994. However, this approach involves a hardware solution, and requires both parties in a communication to be active participants in the escrow operation.
Another key escrow scheme, also applicable to network communications devices, is disclosed by Jim Omura, xe2x80x9cAlternatives to RSA Using Diffie-Hellman with DSS,xe2x80x9d White Paper, Cylink, September 1995. In this scheme, the escrowing party sends the key to an escrow agent, and the agent in return provides the escrowing party a public number to use in the next Diffie-Hellman exchange. However, this scheme involves the escrow of a single key and requires interaction with the escrow agent for each key.
In light of the above shortcomings of prior art techniques in encryption key escrowing, there is a need for an implementation that allows a complete recovery of all encryption keys involved in Diffie-Hellman exchanges and yet still prevents eavesdroppers and intermeddlers from capturing the secrets of private communications. In accordance with an embodiment, there are no special headers or messages required between parties for secure communications. Neither is there a special hardware requirement for any party involved in the communications.
There is also a need to provide a key-escrowing scheme that requires only a single interaction with the escrow agent during a time period of variable length and eliminates the needs to escrow each and every key, and where there is no necessity to store all of the session keys while preserving the ephemeral nature of these keys.
There is also a need to remove the requirement that a participating networking communication device maintain session keys after the life of the session has passed, and thereby to retain the ephemeral nature of the keys.
There is also a need to allow a party to take part in an escrow and to continue inter-operating with existing standards and methods of secured communications.
There is also a need to allow a solution that is applicable to all devices on a network, including hosts, servers and routers.
There is also a need to allow third party law enforcement officers to recover communication information and to monitor messages exchanged between the parties taking part in the Diffie-Hellman communications.
There is also a need to allow recovery of the communication even if only one party was involved in the escrowing scheme.
There is also a need to maintain the security strength of the Diffie-Hellman exchange.
There is also a need to escrow the key to the escrowing center with confidentiality and proof of ownership, thereby assuring both privacy and authenticity of the escrowed information.
The foregoing needs, and other needs that will become apparent from the following description and the appended claims, are fulfilled by the present invention, which comprises, in one aspect, a method of regenerating ephemeral secret keys for Diffie-Hellman communication sessions. A key regeneration method enables a third party xe2x80x9cLxe2x80x9d (such as a law enforcement officer) to gain access to communications previously exchanged between a party xe2x80x9cAxe2x80x9d and any other parties e.g. xe2x80x9cBxe2x80x9d or xe2x80x9cC.xe2x80x9d Party A initially makes a private value Xa available to the third party L and, in one embodiment, party A escrows Xa to an escrow center, where the private value Xa is kept secret and made available only to third party L. Party A may then engage in any number of Diffie-Hellman exchanges with any remote parties in a plurality of communication sessions for a time period t.
For the first communication session between party A and another party B after the escrowing of private value Xa to the escrow center and prior to the conclusion of the period t, party A generates public value Ya from the equation:
Ya=g(Xa+n)modp,
where n equals a value such as 0, while party B generates public value Yb from the equation:
Yb=gXbmodp
The parties A and B provide their respective public values Ya and Yb to the other party, i.e., Ya to party B and Yb to party A. Both parties A and B then generate, respectively, a secret key Kab and Kba for their secret communication session, where:                               K          ⁢                      xe2x80x83                    ⁢          a          ⁢                      xe2x80x83                    ⁢          b                =                  Y          ⁢                      xe2x80x83                    ⁢                      b                          X              ⁢                              xe2x80x83                            ⁢              a                                ⁢                      xe2x80x83                    ⁢          mod          ⁢                      xe2x80x83                    ⁢          p                                                  =                                    K              ⁢                              xe2x80x83                            ⁢              b              ⁢                              xe2x80x83                            ⁢              a                        ⁢                          xe2x80x83                        =                          xe2x80x83                        ⁢                                          Y                ⁢                                  xe2x80x83                                ⁢                                  a                                      X                    ⁢                                          xe2x80x83                                        ⁢                    b                                                  ⁢                                  xe2x80x83                                ⁢                mod                ⁢                                  xe2x80x83                                ⁢                p                            =              K                                      ,            
such that K is a common secret key for both parties. For each of the successive communication sessions, whether to party B or to any other party C, for example, party A generates public value Ya from the same equation Ya=g(Xa+n)mod p, where n is a new value. The new value n may be created, for example, by increasing a previous value of n by 1. Party C generates public value Yc from the equation Yc=gXcmod p, where Xc is a random value of sufficient entropy to guarantee the strength of the secret value K.
When the third party L desires to gain access to communications between the party A and any other party B or C, third party L needs to regenerate the secret key Kab involved in the communication between party A and party B. Party L then obtains Xa from the escrow center and public values Ya and Yb associated with the communication session that party L desires to gain access to. For example, party L eavesdrops directly on the exchange which was done without encryption. In one method, party L calculates secret key Kab using the equation Kab=Yb(Xa+n)mod p. Party L selects a value for n, such as 0 or some other value. Party L calculates Kab and tries to access the desired communication session. If unsuccessful, party L then changes n, for example, by incrementing n by one from the previous value of n. Party L then recalculates Kab until party L is successful in acquiring Kab.
In another aspect, party L calculates secret key Kab using the same equation Kab=Yb(Xa+n)mod p, but by first obtaining n from the equation Y=g(Xa+n)mod p. In one embodiment, party L sets n equal 0, calculates Y, then compares Y to Ya. If Y does not equal to Ya, party L changes n, for example, by incrementing n by one from a previous value of n. Party L then recalculates Y until Y equals Ya. When Y equals Ya, party L has acquired the value for n, and then calculates Kab=Yb(Xa+n)mod p with the acquired n and the previously known values of Yb and Xa.
After time period t has elapsed, a new value Xa is derived and escrowed with the escrow agent. Time period t can be based on the time between escrows or a value v such that a re-escrow is performed when n=v.